{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Movement of Robots"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #brainteaser #array #prefix-sum #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #脑筋急转弯 #数组 #前缀和 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumDistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #移动机器人"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一些机器人分布在一条无限长的数轴上，他们初始坐标用一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;表示。当你给机器人下达命令时，它们以每秒钟一单位的速度开始移动。</p>\n",
    "\n",
    "<p>给你一个字符串&nbsp;<code>s</code>&nbsp;，每个字符按顺序分别表示每个机器人移动的方向。<code>'L'</code>&nbsp;表示机器人往左或者数轴的负方向移动，<code>'R'</code>&nbsp;表示机器人往右或者数轴的正方向移动。</p>\n",
    "\n",
    "<p>当两个机器人相撞时，它们开始沿着原本相反的方向移动。</p>\n",
    "\n",
    "<p>请你返回指令重复执行 <code>d</code>&nbsp;秒后，所有机器人之间两两距离之和。由于答案可能很大，请你将答案对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;取余后返回。</p>\n",
    "\n",
    "<p><b>注意：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>对于坐标在&nbsp;<code>i</code> 和&nbsp;<code>j</code>&nbsp;的两个机器人，<code>(i,j)</code>&nbsp;和&nbsp;<code>(j,i)</code>&nbsp;视为相同的坐标对。也就是说，机器人视为无差别的。</li>\n",
    "\t<li>当机器人相撞时，它们 <strong>立即改变</strong>&nbsp;它们的前进方向，这个过程不消耗任何时间。</li>\n",
    "\t<li>\n",
    "\t<p>当两个机器人在同一时刻占据相同的位置时，就会相撞。</p>\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li>\n",
    "\t\t<p>例如，如果一个机器人位于位置 0 并往右移动，另一个机器人位于位置 2 并往左移动，下一秒，它们都将占据位置 1，并改变方向。再下一秒钟后，第一个机器人位于位置 0 并往左移动，而另一个机器人位于位置 2 并往右移动。</p>\n",
    "\t\t</li>\n",
    "\t\t<li>\n",
    "\t\t<p>例如，如果一个机器人位于位置 0 并往右移动，另一个机器人位于位置 1 并往左移动，下一秒，第一个机器人位于位置 0 并往左行驶，而另一个机器人位于位置 1 并往右移动。</p>\n",
    "\t\t</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [-2,0,2], s = \"RLL\", d = 3\n",
    "<b>输出：</b>8\n",
    "<b>解释：</b>\n",
    "1 秒后，机器人的位置为 [-1,-1,1] 。现在下标为 0 的机器人开始往左移动，下标为 1 的机器人开始往右移动。\n",
    "2 秒后，机器人的位置为 [-2,0,0] 。现在下标为 1 的机器人开始往左移动，下标为 2 的机器人开始往右移动。\n",
    "3 秒后，机器人的位置为 [-3,-1,1] 。\n",
    "下标为 0 和 1 的机器人之间距离为 abs(-3 - (-1)) = 2 。\n",
    "下标为 0 和 2 的机器人之间的距离为 abs(-3 - 1) = 4 。\n",
    "下标为 1 和 2 的机器人之间的距离为 abs(-1 - 1) = 2 。\n",
    "所有机器人对之间的总距离为 2 + 4 + 2 = 8 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,0], s = \"RL\", d = 2\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>\n",
    "1 秒后，机器人的位置为 [2,-1] 。\n",
    "2 秒后，机器人的位置为 [3,-2] 。\n",
    "两个机器人的距离为 abs(-2 - 3) = 5 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-2 * 10<sup>9</sup>&nbsp;&lt;= nums[i] &lt;= 2 * 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 &lt;= d &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>nums.length == s.length&nbsp;</code></li>\n",
    "\t<li><code>s</code>&nbsp;只包含&nbsp;<code>'L'</code> 和 <code>'R'</code>&nbsp;。</li>\n",
    "\t<li><code>nums[i]</code>&nbsp;互不相同。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [movement-of-robots](https://leetcode.cn/problems/movement-of-robots/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [movement-of-robots](https://leetcode.cn/problems/movement-of-robots/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-2,0,2]\\n\"RLL\"\\n3', '[1,0]\\n\"RL\"\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        n = len(nums)\n",
    "        pos = [0]*n\n",
    "        mod = 10**9+7\n",
    "        for i in range(n):\n",
    "            if s[i] == 'L':\n",
    "                pos[i] = nums[i]-d\n",
    "            else:\n",
    "                pos[i] = nums[i]+d\n",
    "        pos.sort()\n",
    "        ret = 0\n",
    "        for i in range(1, n):\n",
    "            ret += (pos[i] - pos[i-1])*i*(n-i)\n",
    "            ret %= mod\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        \n",
    "\n",
    "        l=len(nums)\n",
    "        for i in range(l):\n",
    "            if s[i]=='L':\n",
    "                nums[i]-=d\n",
    "            else:\n",
    "                nums[i]+=d\n",
    "        \n",
    "\n",
    "        res=0\n",
    "        nums.sort()\n",
    "        for i in range(l-1):\n",
    "            nums[i]=nums[i+1]-nums[i]\n",
    "        \n",
    "        \n",
    "        l-=1\n",
    "        for i in range(l):\n",
    "            res+= nums[i] * (i+1)*(l-i)\n",
    "\n",
    "        \n",
    "        res%=10**9+7\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        \"\"\"\n",
    "        其实两个机器人相撞后完全可以看作穿过对方继续前行\n",
    "        直接根据方向 d，得出走后的距离\n",
    "        排序，点按照位置从左到右\n",
    "        想一下每加一个点，需要加多少份距离:\n",
    "        a1\n",
    "        a1 + 2a2\n",
    "        a1 + 2a2 + 3a3\n",
    "        a1 + 2a2 + 3a3 + 4a4\n",
    "        ...\n",
    "        最终所有的点所需要加的距离和为:\n",
    "        (1*n)a1 + (2*(n-1))a2 + (3*(n-2))a3 + ... + (n*1)an\n",
    "        因为 n 个点有 n-1 段距离，如果距离从 1 开始算，那么所以对于 n 个点应该为：\n",
    "        (1*(n-1))a1 + (2*(n-2))a2 + ... + ((n-1)*1)an-1\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            nums[i] += d if s[i] == 'R' else -d\n",
    "        nums.sort()\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            nums[i] = nums[i] - nums[i - 1]\n",
    "        ans = 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(1, n):\n",
    "            ans = ((i * (n - i) * nums[i]) % mod + ans) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        for i,c in enumerate(s):\n",
    "            nums[i] += d if c==\"R\" else -d\n",
    "        nums.sort()\n",
    "        total_distance = s = 0\n",
    "        for i,c in enumerate(nums):\n",
    "            total_distance += i*c-s\n",
    "            s += c\n",
    " \n",
    "        return total_distance % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        \"\"\"\n",
    "        其实两个机器人相撞后完全可以看作穿过对方继续前行\n",
    "        直接根据方向 d，得出走后的距离\n",
    "        排序，点按照位置从左到右\n",
    "        想一下每加一个点，需要加多少份距离:\n",
    "        a1\n",
    "        a1 + 2a2\n",
    "        a1 + 2a2 + 3a3\n",
    "        a1 + 2a2 + 3a3 + 4a4\n",
    "        ...\n",
    "        最终所有的点所需要加的距离和为:\n",
    "        (1*n)a1 + (2*(n-1))a2 + (3*(n-2))a3 + ... + (n*1)an\n",
    "        因为 n 个点有 n-1 段距离，如果距离从 1 开始算，那么所以对于 n 个点应该为：\n",
    "        (1*(n-1))a1 + (2*(n-2))a2 + ... + ((n-1)*1)an-1\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            nums[i] += d if s[i] == 'R' else -d\n",
    "        nums.sort()\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            nums[i] = nums[i] - nums[i - 1]\n",
    "        ans = 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(1, n):\n",
    "            ans += (i * (n - i) * nums[i])\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        \"\"\"\n",
    "        其实两个机器人相撞后完全可以看作穿过对方继续前行\n",
    "        直接根据方向 d，得出走后的距离\n",
    "        排序，点按照位置从左到右\n",
    "        想一下每加一个点，需要加多少份距离:\n",
    "        a1\n",
    "        a1 + 2a2\n",
    "        a1 + 2a2 + 3a3\n",
    "        a1 + 2a2 + 3a3 + 4a4\n",
    "        ...\n",
    "        最终所有的点所需要加的距离和为:\n",
    "        (1*n)a1 + (2*(n-1))a2 + (3*(n-2))a3 + ... + (n*1)an\n",
    "        因为 n 个点有 n-1 段距离，如果距离从 1 开始算，那么所以对于 n 个点应该为：\n",
    "        (1*(n-1))a1 + (2*(n-2))a2 + ... + ((n-1)*1)an-1\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            nums[i] += d if s[i] == 'R' else -d\n",
    "        nums.sort()\n",
    "        mod = 10 ** 9 + 7\n",
    "        return sum((nums[i] - nums[i - 1]) * i * (n - i) for i in range(1, n)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            nums[i] += d if s[i] == 'R' else -d\n",
    "        nums.sort()\n",
    "\n",
    "        ans = pre_num =0\n",
    "        for i, x in enumerate(nums):\n",
    "            ans+= i * x - pre_num \n",
    "            pre_num += x\n",
    "        return ans % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        location = [nums[_] - d if s[_] == 'L' else nums[_] + d for _ in range(len(nums))]\n",
    "        location.sort()\n",
    "\n",
    "        def cal_distance(location: list, res: int) -> int:\n",
    "            last_distance = 0\n",
    "            for index in range(1, len(nums)):\n",
    "                cur_distance = abs(location[index] - location[index - 1])\n",
    "                res += index * cur_distance + last_distance\n",
    "                last_distance = index * cur_distance + last_distance\n",
    "            return res\n",
    "\n",
    "        return cal_distance(location, 0) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        n=len(nums)\n",
    "        for i in range(n):nums[i]+=d*(1 if s[i]=='R' else -1)\n",
    "        nums.sort()\n",
    "        ans=sum(nums)-nums[0]*n;pans=ans\n",
    "        for i in range(1,n):\n",
    "            pans+=(nums[i]-nums[i-1])*(2*i-n)\n",
    "            ans+=pans\n",
    "        return (ans//2)%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            nums[i] += d if s[i] == 'R' else -d\n",
    "        nums.sort()\n",
    "        \n",
    "        ans = pre = 0\n",
    "        for i in range(n):\n",
    "            ans += nums[i] * i - pre\n",
    "            pre += nums[i]\n",
    "        return ans % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        mod=10**9+7\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            if s[i]==\"R\":\n",
    "                nums[i]+=d\n",
    "            else:\n",
    "                nums[i]-=d\n",
    "        nums.sort()\n",
    "        ans=0\n",
    "        for i in range(1,n):\n",
    "            ans+=(nums[i]-nums[i-1])*i*(n-i)\n",
    "            ans%=mod\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if s[i] == 'L': nums[i] -= d\n",
    "            else: nums[i] += d\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            cur = nums[i] - nums[i - 1]\n",
    "            ans = (ans + cur * i * (n - i)) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        pos = [nums[i] - d if s[i] == 'L' else nums[i] + d for i in range(n)]\n",
    "        pos.sort()\n",
    "        # return sum([(pos[i] - pos[i - 1]) * i * (n - i) for i in range(1, n)])%mod\n",
    "        res = 0\n",
    "        for i in range(1,len(nums)):\n",
    "            res += ((n-i)*(i)*(pos[i]-pos[i-1]))%mod\n",
    "        return res%mod  \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        for i, c in enumerate(s):\n",
    "            nums[i] += d if c == 'R' else -d\n",
    "        nums.sort()\n",
    "\n",
    "        BASE = 10 ** 9 + 7\n",
    "        ans = pre_dis_sum = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            ans = (ans + x * i - pre_dis_sum) % BASE\n",
    "            pre_dis_sum = (pre_dis_sum + x) % BASE\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        n=len(nums)\n",
    "        orders=list(s)\n",
    "        for i in range(n):\n",
    "            if orders[i]=='R':\n",
    "                nums[i]+=d\n",
    "            else:\n",
    "                nums[i]-=d\n",
    "        \n",
    "        result=0\n",
    "        nums.sort()\n",
    "        for i in range(1,n):\n",
    "            result+=(nums[i]-nums[i-1])*(i*(n-i))\n",
    "        \n",
    "        return result%(10**9+7)\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        n = len(nums)\n",
    "        m = 1e9 + 7\n",
    "        # 先移动\n",
    "        for i in range(n):\n",
    "            if s[i] == \"R\":\n",
    "                nums[i] += d\n",
    "            else:\n",
    "                nums[i] -= d\n",
    "        # 计算总距离\n",
    "        total_num = 0\n",
    "        # 对列进行排序\n",
    "        nums.sort()\n",
    "        # 进行距离计算\n",
    "        i = 0\n",
    "        j = n-1\n",
    "        while i<j:\n",
    "            total_num = (total_num%m + (j-i)*(nums[j]-nums[i])%m)%m\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return int(total_num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        for i ,c in enumerate(s):\n",
    "            if c == \"L\":\n",
    "                nums[i] -= d\n",
    "            else:\n",
    "                nums[i] += d\n",
    "        nums.sort()\n",
    "        result = 0\n",
    "        s = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            result += i*x -s\n",
    "            s += x\n",
    "        return result%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        left = [nums[i] - d for i in range(len(nums)) if s[i] == 'L']\n",
    "        right = [nums[i] + d for i in range(len(nums)) if s[i] == 'R']\n",
    "        nums = sorted(left + right)\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            res = (res + (2 * i - len(nums) + 1) * nums[i]) % mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        #1.先弄出所有机器人的位置\n",
    "        #2.再用贡献法o（n）求出距离\n",
    "\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            nums[i] += d if s[i] == \"R\" else -d\n",
    "        nums.sort()\n",
    "        # for i in range(1,n):\n",
    "        #     #i 表示左边的个数\n",
    "        #     res += i*(n-i)*(nums[i]-nums[i-1])\n",
    "        # # print(nums)\n",
    "        pre_sum = 0\n",
    "        res = 0\n",
    "        print(nums)\n",
    "        for i,v in enumerate(nums):\n",
    "            res += i*v\n",
    "            res -= pre_sum\n",
    "            pre_sum += nums[i]\n",
    "            print(res)\n",
    "        return res % (10**9 +7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        for i,c in enumerate(s):\n",
    "            nums[i]+=d if c=='R' else -d\n",
    "        nums.sort()\n",
    "        ans=s=0\n",
    "        for i,x in enumerate(nums):\n",
    "            ans+=i*x-s\n",
    "            s+=x\n",
    "        return ans%(10**9+7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        for i, c in enumerate(s):\n",
    "            nums[i] += d if c == \"R\" else -d\n",
    "        print(nums)\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        ans = s = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            ans += i * x - s\n",
    "            s += x\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        pos = []\n",
    "        for i in range(len(nums)):\n",
    "            if s[i] == 'R':\n",
    "                pos.append(nums[i] + d)\n",
    "            else:\n",
    "                pos.append(nums[i] - d)\n",
    "        pos.sort()\n",
    "        res = 0\n",
    "        n = len(pos)\n",
    "        for i in range(len(pos)):\n",
    "            res += (i*pos[i] - (n - i - 1)*pos[i]) % (10**9 + 7)\n",
    "        return res % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        pos = [nums[i] - d if s[i] == 'L' else nums[i] + d for i in range(n)]\n",
    "        pos.sort()\n",
    "        ans = 0\n",
    "        for i in range(1, len(pos)):\n",
    "            ans += (pos[i]-pos[i-1])*i*(n-i)\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        mod = (10**9)+7\n",
    "        li = []\n",
    "        for i,j in zip(nums,s):\n",
    "            if j == \"R\":\n",
    "                li.append(i+d)\n",
    "            else:\n",
    "                li.append(i-d)\n",
    "        li.sort(reverse=True)\n",
    "        ans = temp = 0\n",
    "        n = len(li)\n",
    "        for i in range(1,n):\n",
    "            temp += (li[i-1]-li[i])*i\n",
    "            ans += temp % mod\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        n = len(nums)\n",
    "        final_pos = []\n",
    "        for num, dirt in zip(nums, s):\n",
    "            final_pos.append(num + (d if dirt == 'R' else -d))\n",
    "        final_pos.sort()\n",
    "        print(\"final_pos -\", final_pos)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        for i, pos in enumerate(final_pos):\n",
    "            if i == n - 1: continue\n",
    "            left_cnt, right_cnt = i + 1, n - i - 1\n",
    "            diff = (final_pos[i + 1] - final_pos[i]) % MOD\n",
    "            print(left_cnt, right_cnt, diff)\n",
    "            ans = (ans + diff * (left_cnt * right_cnt) % MOD) % MOD\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        pos = []\n",
    "        index = 0\n",
    "        for i in nums:\n",
    "            if s[index] == \"R\":\n",
    "                pos.append(i + d)\n",
    "            else:\n",
    "                pos.append(i - d)\n",
    "            index += 1\n",
    "        pos.sort()\n",
    "        res = s = 0\n",
    "        mod = 10**9+7\n",
    "        for i,x in enumerate(pos):\n",
    "            res += i * x - s\n",
    "            s += x\n",
    "        return res % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        \"\"\" 碰撞即是穿透 相对位置不变 \"\"\"\n",
    "        # calculate new position after tranverse \n",
    "        for idx, act in enumerate(s):\n",
    "            if act == 'R':\n",
    "                nums[idx] += d \n",
    "            elif act == 'L':\n",
    "                nums[idx] -= d \n",
    "        \n",
    "        nums.sort()  # -3 -1 1 \n",
    "        # print(nums)\n",
    "        # ans = prefixSum = 0\n",
    "        # for idx, pos in enumerate(nums):\n",
    "        #     ans += idx*pos - prefixSum  # 2 + 6 \n",
    "        #     prefixSum += pos  # -4 \n",
    "        mod = (10**9+7)\n",
    "        n = len(nums)\n",
    "\n",
    "        return sum([(nums[i] - nums[i - 1]) * i * (n-i) for i in range(1, n)]) % mod \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        \"\"\" 碰撞即是穿透 相对位置不变 \"\"\"\n",
    "        # calculate new position after tranverse \n",
    "        for idx, act in enumerate(s):\n",
    "            if act == 'R':\n",
    "                nums[idx] += d \n",
    "            elif act == 'L':\n",
    "                nums[idx] -= d \n",
    "        \n",
    "        nums.sort()  # -3 -1 1 \n",
    "        # print(nums)\n",
    "        # ans = prefixSum = 0\n",
    "        # for idx, pos in enumerate(nums):\n",
    "        #     ans += idx*pos - prefixSum  # 2 + 6 \n",
    "        #     prefixSum += pos  # -4 \n",
    "        mod = (10**9+7)\n",
    "        n = len(nums)\n",
    "\n",
    "        return sum([(nums[i] - nums[i - 1]) * i * (n-i) for i in range(1, n)]) % mod \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        for i in range(n):  \n",
    "            if s[i] == 'L': nums[i] -= d \n",
    "            else: nums[i] += d \n",
    "        nums.sort()\n",
    "        return sum([(nums[i] - nums[i - 1]) * i * (n - i) for i in range(1, n)]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if s[i] == 'L':\n",
    "                nums[i] -= d \n",
    "            else:\n",
    "                nums[i] += d \n",
    "        nums.sort()\n",
    "        nums[0] = nums[1] - nums[0]\n",
    "        for i in range(1, n - 1):\n",
    "            nums[i] = nums[i - 1] + (nums[i + 1] - nums[i]) * (i + 1)\n",
    "        nums[-1] = 0\n",
    "        return sum(nums) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if s[i] == 'L':\n",
    "                nums[i] -= d \n",
    "            else:\n",
    "                nums[i] += d \n",
    "        nums.sort()\n",
    "        nums[0] = nums[1] - nums[0]\n",
    "        for i in range(1, n - 1):\n",
    "            nums[i] = nums[i - 1] + (nums[i + 1] - nums[i]) * (i + 1)\n",
    "        nums[-1] = 0\n",
    "        return sum(nums) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        n = len(nums)\n",
    "        for i, c in zip(list(range(n)), s):\n",
    "            if c == 'R':\n",
    "                nums[i] += d\n",
    "            else:\n",
    "                nums[i] -= d\n",
    "        res = 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        for i in range(n - 1):\n",
    "            res = (res + (nums[i + 1] - nums[i]) * (i + 1) * (n - i - 1)) % MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        n=len(nums)\n",
    "        dir={'L':-1,'R':1}\n",
    "        for i in range(n):\n",
    "            nums[i]+=dir[s[i]]*d\n",
    "        nums.sort()\n",
    "\n",
    "        pre_nums=[0]*n\n",
    "        pre_nums[n-1]=nums[-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            pre_nums[i]+=pre_nums[i+1]+nums[i]\n",
    "        # print(nums)\n",
    "        # print(pre_nums)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            ans+=pre_nums[i]-nums[i]*(n-i)\n",
    "            # print(ans)\n",
    "        return ans%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if s[i] == 'L':\n",
    "                nums[i] -= d\n",
    "            else:\n",
    "                nums[i] += d\n",
    "        nums.sort()\n",
    "        res = [0] * n\n",
    "        for i in range(1, n):\n",
    "            res[i] = res[i-1] + i*(nums[i] - nums[i-1])\n",
    "        return sum(res)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        for i, diraction in enumerate(s):\n",
    "            if diraction == 'R':\n",
    "                nums[i] += d\n",
    "            else:\n",
    "                nums[i] -= d\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        distance = []\n",
    "        for i in range(n-1):\n",
    "            distance.append(nums[i+1] - nums[i])\n",
    "        print(distance)\n",
    "        for i, dis in enumerate(distance):\n",
    "            ans = (ans + (n-1-i) * dis*(i+1)) % (10**9+7)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] += d if s[i] == 'R' else -d\n",
    "        nums.sort()\n",
    "        # 动态规划求到之前所有距离之和\n",
    "        dp = [0]\n",
    "        for i in range(1, len(nums)):\n",
    "            dp.append(dp[-1] + (nums[i] - nums[i-1]) * i)\n",
    "        return int(sum(dp) % 1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "\n",
    "        step = []\n",
    "        for i in range(len(nums)):\n",
    "            if s[i] == 'R':\n",
    "                step.append(1)\n",
    "            else:\n",
    "                step.append(-1)\n",
    "\n",
    "        step = [i * d for i in step]\n",
    "\n",
    "        nums = [i + j for i, j in zip(nums, step)]\n",
    "        ans = 0\n",
    "        mid = int(len(nums) / 2)\n",
    "        nums.sort()\n",
    "        for i in range(mid):\n",
    "            ans += (len(nums) - 1 - 2 * i) * abs(nums[len(nums) - 1 - i] - nums[i])\n",
    "        res = ans\n",
    "        return res % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        n = len(nums)\n",
    "        pos = [nums[i] - d if s[i]==\"L\" else nums[i] + d for i in range(n)]\n",
    "        pos.sort()\n",
    "        return sum([(pos[i] - pos[i-1]) * i * (n-i) for i in range(1,n)]) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        pos = [nums[i] - d if s[i] == 'L' else nums[i] + d for i in range(n)]\n",
    "        pos.sort()\n",
    "        return sum([(pos[i] - pos[i - 1]) * i * (n - i) for i in range(1, n)]) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        pos = [nums[i] - d if s[i] == 'L' else nums[i] + d for i in range(n)]\n",
    "        pos.sort()\n",
    "        return sum([(pos[i] - pos[i - 1]) * i * (n - i) for i in range(1, n)])%mod\n",
    "        # res = 0\n",
    "        # for i in range(len(nums)-1):\n",
    "        #     res += ((n-i-1)*(i+1)*(pos[i+1]-pos[i]))%(10**9+7)\n",
    "        # return int(res)    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        pos = [nums[i] - d if s[i] == 'L' else nums[i] + d for i in range(n)]\n",
    "        pos.sort()\n",
    "        return sum([(pos[i] - pos[i - 1]) * i * (n - i) for i in range(1, n)]) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        mod=10**9+7 #题目要求的\n",
    "        n=len(nums) #判断一共有多少的小车\n",
    "        pos=[nums[i]-d if s[i]==\"L\" else nums[i]+d for i in range(n)]\n",
    "        pos.sort()\n",
    "        return sum([(pos[i] - pos[i - 1]) * i * (n - i) for i in range(1, n)])%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        mod_num = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        #dir_list = [1 if s[i]=='R' else -1 for i in range(n)]\n",
    "        '''for i in range(d):\n",
    "            for j in range(len(nums)):\n",
    "                nums[j] += dir_list[j]\n",
    "            for j in range(len(nums)-1):\n",
    "                if nums[j] == nums[j+1]:\n",
    "                    dir_list[j] = -dir_list[j]\n",
    "                    dir_list[j+1] = -dir_list[j]'''\n",
    "\n",
    "        #for j in range(n):\n",
    "         #   nums[j] += d * dir_list[j]\n",
    "        pos = [nums[i] - d if s[i] == 'L' else nums[i] + d for i in range(n)]\n",
    "        '''sum_dist = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i, len(nums)):\n",
    "                sum_dist += abs(nums[i]-nums[j])'''\n",
    "        pos.sort()\n",
    "        sum_dist = sum([(pos[i]-pos[i-1]) * i * (n-i) for i in range(1, n)])\n",
    " \n",
    "        return int(sum_dist%mod_num)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        pos = [nums[i] - d if s[i] == 'L' else nums[i] + d for i in range(n)]\n",
    "        pos.sort()\n",
    "        return sum([(pos[i] - pos[i - 1]) * i * (n - i) for i in range(1, n)]) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int: \n",
    "        for i,c in enumerate(s):\n",
    "            if c=='L':\n",
    "                nums[i] -=d \n",
    "            else:\n",
    "                nums[i] += d\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        r = nums[-1]-nums[0]\n",
    "        l = nums[0]\n",
    "        for i in range(n):\n",
    "            nums[i] -= l\n",
    "        presum = list( accumulate(nums ) ) \n",
    "        ans = 0\n",
    "        \n",
    "        for i,num in enumerate(nums):\n",
    "            if i>0:\n",
    "                ans += num*i - presum[i-1] \n",
    "                ans %= 1_000_000_007\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums, s: str, d: int) -> int:\n",
    "        s = list(s)\n",
    "        res = 0\n",
    "        b = []\n",
    "        for i in s:\n",
    "            if i == \"R\":\n",
    "                b.append(1)\n",
    "            else:\n",
    "                b.append(-1)\n",
    "        b = list(map(lambda x:x*d,b))\n",
    "        n = len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] += b[i]\n",
    "        nums.sort()\n",
    "        res = sum([(nums[i] - nums[i - 1]) * i * (n - i) for i in range(1, n)])\n",
    "        return res % (10**9+7)\n",
    "S = Solution()\n",
    "print(S.sumDistance(nums = [1,0], s = \"RL\", d = 2\n",
    "))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if s[i] == 'R':\n",
    "                nums[i] += d\n",
    "            else:\n",
    "                nums[i] -= d\n",
    "        nums = sorted(nums)\n",
    "        m = [0]*n\n",
    "        for i in range(1, n):\n",
    "           m[i] =  (nums[i]-nums[i-1])*i*(n-i)\n",
    "        print(m)\n",
    "        return sum(m) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        ans = 1e9 + 7\n",
    "        length = len(nums)\n",
    "        sum = 0\n",
    "        temp = [0] * length\n",
    "        num2 = [0] * length\n",
    "        for i in range(length):\n",
    "            if s[i] == 'R':\n",
    "                  num2[i] = nums[i] + d\n",
    "            else:\n",
    "                num2[i] = nums[i] - d\n",
    "        num2.sort()\n",
    "        for i in range(1, length):\n",
    "            temp[i] = (temp[i-1] + i * (num2[i] - num2[i-1])) % ans\n",
    "        for i in range(length):\n",
    "            sum = (sum + temp[i]) % ans\n",
    "        return int(sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        #mod_num = 1e9 + 7\n",
    "        mod_num = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        dir_list = [1 if s[i]=='R' else -1 for i in range(n)]\n",
    "        '''for i in range(d):\n",
    "            for j in range(len(nums)):\n",
    "                nums[j] += dir_list[j]\n",
    "            for j in range(len(nums)-1):\n",
    "                if nums[j] == nums[j+1]:\n",
    "                    dir_list[j] = -dir_list[j]\n",
    "                    dir_list[j+1] = -dir_list[j]'''\n",
    "\n",
    "        nums = [nums[i]-d if s[i] == 'L' else nums[i] + d for i in range(n)]\n",
    "\n",
    "        '''sum_dist = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i, len(nums)):\n",
    "                sum_dist += abs(nums[i]-nums[j])'''\n",
    "        nums.sort()\n",
    "        sum_dist = sum([(nums[i]-nums[i-1]) * i * (n-i) for i in range(1, n)])\n",
    " \n",
    "        return int(sum_dist%mod_num)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        n = len(nums)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        pos = list(sorted(num - d if dire == 'L' else num + d for num, dire in zip(nums, s)))\n",
    "\n",
    "        res = [0] * n\n",
    "        for i in range(n):\n",
    "            res[i] = (pos[i] - pos[i - 1]) * i * (n - i) % MOD\n",
    "\n",
    "        return sum(res) % MOD\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "# RLL\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        nums = sorted([nums[i] + d if s[i] == \"R\" else nums[i] - d for i in range(len(nums))])\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        sub_dis = []\n",
    "        for i in range(1, n):\n",
    "            sub_dis.append(nums[i] - nums[i - 1])\n",
    "\n",
    "        for i in range(1, n):\n",
    "            ans += sub_dis[i - 1] * (n - i) * i\n",
    "\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(k + (d if j == \"R\" else -d) for k, j in zip(nums, s))\n",
    "        nums = [b-a for a,b in zip(nums,nums[1:])]\n",
    "        ans = 0\n",
    "        mod = 10**9+7\n",
    "        for i,j in enumerate(nums,1):\n",
    "            ans = (ans + j * (n-i)*i)%mod\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "    n = len(nums)\n",
    "    for i in range(n):\n",
    "      if s[i] == 'R': nums[i] += d\n",
    "      else: nums[i] -= d \n",
    "    nums.sort()\n",
    "\n",
    "    an = [0 for _ in range(n - 1)]\n",
    "    for i in range(n - 1):\n",
    "      an[i] = (n - 1) * (i + 1) - (i * (i + 1))\n",
    "    \n",
    "    r = [0 for _ in range(n - 1)]\n",
    "    for i in range(n - 1):\n",
    "      r[i] = abs(nums[i + 1] - nums[i])\n",
    "\n",
    "    ans = 0\n",
    "    for i in range(n - 1):\n",
    "      ans += an[i] * r[i]\n",
    "      ans %= 10 ** 9 + 7\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(k + (d if j == \"R\" else -d) for k, j in zip(nums, s))\n",
    "        nums = [b-a for a,b in zip(nums,nums[1:])]\n",
    "        ans = 0\n",
    "        mod = 10**9+7\n",
    "        for i,j in enumerate(nums, 1):\n",
    "            ans = (ans + j * (n - i) * i) % mod\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "    n = len(nums)\n",
    "    for i in range(n):\n",
    "      if s[i] == 'R': nums[i] += d\n",
    "      else: nums[i] -= d \n",
    "    nums.sort()\n",
    "\n",
    "    an = [0 for _ in range(n - 1)]\n",
    "    for i in range(n - 1):\n",
    "      an[i] = (n - 1) * (i + 1) - (i * (i + 1))\n",
    "    \n",
    "    r = [0 for _ in range(n - 1)]\n",
    "    for i in range(n - 1):\n",
    "      r[i] = abs(nums[i + 1] - nums[i])\n",
    "\n",
    "    ans = 0\n",
    "    for i in range(n - 1):\n",
    "      ans += an[i] * r[i]\n",
    "      ans %= 10 ** 9 + 7\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        pos = [nums[i] - d if s[i] == \"L\" else nums[i] + d for i in range(len(nums))]\n",
    "        pos.sort()\n",
    "        return sum([((pos[i] - pos[i - 1]) * i * (len(pos) - i)) % mod for i in range(1, len(pos))]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        pos = sorted([nums[i] - d if s[i] == 'L' else nums[i] + d for i in range(len(nums))])\n",
    "        return sum([(pos[i] - pos[i - 1]) * i * (len(nums) - i) % (10 ** 9 + 7) for i in range(1, len(nums))]) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        return (-sum(nums:=sorted([nums[i] + (d if s[i] == 'R' else -d)for i in range(len(s))]))*(len(s)-1)+sum([nums[i]*i for i in range(len(s))])*2)%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        pos = [nums[i] + d if s[i] == 'R' else nums[i] - d for i in range(0, n)]\n",
    "        pos.sort()\n",
    "        return sum([(2 * i - n + 1) * pos[i] for i in range(0, n)]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        assert 2 <= len(nums) <= 10**5\n",
    "        for i in nums:\n",
    "            assert -2 *10**9 <= i <= 2*10**9\n",
    "        assert 0 <= d <= 10**9\n",
    "        assert len(nums) ==len(s)\n",
    "        for i in s:\n",
    "            assert i in \"RL\"\n",
    "        assert len(nums) == len(set(nums))\n",
    "    \n",
    "        flist = []\n",
    "        for pos, w in zip(nums, s):\n",
    "            tmp = 1 if w =='R' else -1 \n",
    "            flist.append(pos+tmp*d)\n",
    "        flist.sort()\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        tmp = 0\n",
    "        MOD = 10**9+7\n",
    "        last = flist[0]\n",
    "        for cur in flist[1:]:\n",
    "            tmp += 1\n",
    "            res += tmp * (n-tmp) * (cur-last) % MOD\n",
    "            last = cur\n",
    "        return res % MOD \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        enums = []\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if s[i]=='R':\n",
    "                enums.append(nums[i]+d)\n",
    "            else:\n",
    "                enums.append(nums[i]-d)\n",
    "        ret = 0\n",
    "        tot = 0\n",
    "        n = 0\n",
    "        enums.sort()\n",
    "        nmin = enums[0]\n",
    "        enums = [x-nmin for x in enums]\n",
    "        for num in enums:\n",
    "            ret += n*num-tot\n",
    "            ret = ret%1000000007\n",
    "            tot+=num\n",
    "            n+=1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1_000_000_007\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        positions = []\n",
    "        for pos, direction in zip(nums, s):\n",
    "            if direction == 'L':\n",
    "                positions.append(pos - d)\n",
    "            else:\n",
    "                positions.append(pos + d)\n",
    "\n",
    "        positions.sort()\n",
    "        prefix = list(accumulate(positions))\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n - 1):\n",
    "            res  += (\n",
    "                prefix[-1] - prefix[i + 1] + positions[i + 1] - \n",
    "                (n - i - 1) * positions[i]\n",
    "            )\n",
    " \n",
    "        return res % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:        \n",
    "        pos = [nums[n] + d if s[n]=='R' else nums[n]-d for n in range(len(nums))]\n",
    "        pos.sort()\n",
    "        forward = [0]*len(nums)\n",
    "        for i in range(1, len(nums)):\n",
    "            forward[i] = ((pos[i]-pos[i-1])*i+forward[i-1]) % 1000000007        \n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            res = (res + forward[i]) % 1000000007\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        n = len(nums)\n",
    "        MOD = 10**9 + 7\n",
    "        tmp = sorted([nums[i] + d if s[i] == 'R' else nums[i] - d for i in range(n)])\n",
    "        res = 0\n",
    "        # 暴力循环会导致超时,利用前缀和相加\n",
    "        pos = [0] * (n+1)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            pos[i] = pos[i+1] + tmp[i]\n",
    "            res += pos[i] - (n-i) * tmp[i]\n",
    "\n",
    "        return res % MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        pos = [n+d if s[i] == 'R' else n-d for i, n in enumerate(nums)]\n",
    "\n",
    "        pos = sorted(pos)\n",
    "\n",
    "        return sum([(pos[i]-pos[i-1])*i*(len(nums)-i) for i in range(1, len(nums))]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        pos = [nums[i] - d if s[i] == 'L' else nums[i] + d for i in range(n)]\n",
    "        pos.sort()\n",
    "        return sum([(pos[i] - pos[i - 1]) * i * (n - i) for i in range(1, n)]) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        n = len(nums)\n",
    "        pos = [num - d if s[idx] == 'L' else num + d  for idx, num in enumerate(nums)]\n",
    "        pos.sort()\n",
    "        return sum([(pos[i] - pos[i-1])*i*(n - i) for i in range(n)])%(10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        pos = [nums[i] - d if s[i] == 'L' else nums[i] + d for i in range(n)]\n",
    "        pos.sort()\n",
    "        return sum([(pos[i] - pos[i - 1]) * i * (n - i) for i in range(1, n)]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        mod=1000000007\n",
    "        n=len(nums)\n",
    "        pos=[nums[i]+d if s[i]=='R' else nums[i]-d for i in range(n)]\n",
    "        pos.sort()\n",
    "        return sum([(pos[i]-pos[i-1])*i*(n-i) for i in range(1,n)]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        pos = [nums[i] - d if s[i] == 'L' else nums[i] + d for i in range(n)]\n",
    "        pos.sort()\n",
    "        return sum([(pos[i] - pos[i - 1]) * i * (n - i) for i in range(1, n)]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        pos = [nums[i] - d if s[i] == 'L' else nums[i] + d for i in range(n)]\n",
    "        pos.sort()\n",
    "        return sum([(pos[i] - pos[i - 1]) * i * (n - i) for i in range(1, n)]) % mod"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
